package _17_剑指Offer;

import java.util.Arrays;

public class _59_剑指OfferI滑动窗口的最大值 {

    public static void main(String[] args) {

        _59_剑指OfferI滑动窗口的最大值 v = new _59_剑指OfferI滑动窗口的最大值();

        int[] ins = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(v.maxSlidingWindow(ins, 3)));

    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k <= 1) return nums;
        int[] maxs = new int[nums.length - k + 1];
        int maxIndex = 0;
        // 求出前k项最大元素的索引值
        for (int i = 1; i < k; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

        for (int begin = 0; begin < maxs.length; begin++) {
            int end = begin + k - 1;
            if (nums[end] > nums[maxIndex]) {
                // 更新最大索引
                maxIndex = end;
            } else if (maxIndex < begin) {
                maxIndex = begin;
                // 最大索引范围不在滑动窗口内
                for (int i = begin + 1; i <= end; i++) {
                    if (nums[i] > nums[maxIndex]) {
                        maxIndex = i;
                    }
                }
            }
            maxs[begin] = nums[maxIndex];
        }
        return maxs;
    }

}
